package com.hy.study.sort;

import java.util.Arrays;

/**
 * 基数排序(桶排序)
 * 是一个个经典的空间换时间的算法
 */
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {52, 3, 542, 748, 14, 214};
    //    int arr[] = new int[800000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
//        }
        System.out.println("---------排序之前---------");
        long startTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println("---------排序之后-------");
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println("---------总共耗时("+(endTime-startTime)/1000+"秒)");
    }

    public static void radixSort(int arr[]) {
        //  找到最大数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int maxLength = (max + "").length();
        for (int m = 0, n = 1; m < maxLength; m++, n *= 10) {
            //1.定义一个桶 为了让值放入数据的时候，防止栈溢出，每一个桶 设置未arr.length 大小

            int[][] bucket = new int[10][arr.length];

            //记录每个桶中实际存放数据的个数
            int[] bucketElementCounts = new int[10];
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个位
                int digitOfElement = arr[j] / n % 10;
                //放入到桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序，将数据放入到原来的数组中
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if (bucketElementCounts[k] != 0) {//有数据的桶里面
                    //说明第K个桶中有数据
                    for (int i = 0; i < bucketElementCounts[k]; i++) {
                        //取出元素放入到arr中
                        arr[index++] = bucket[k][i];

                    }

                }
                bucketElementCounts[k] = 0;//将临时数组归0 方便下次使用。
            }

        }
    }


}
